#include <vector>
#include <list>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <fstream>
#include <set>
#include "tree.h"

using namespace std;

void inOrder(Tree *root)
{
    stack<Tree *> myStack;
    Tree *cur = root;

    while(!myStack.empty() || cur) {
        if (cur) {
            myStack.push(cur);
            cur = cur->left;
        } else {
            Tree *top = myStack.top();
            myStack.pop();
            cout << top->data << " ";
            cur = top->right;
        }
    }
}

void preOrder(Tree *root)
{
    stack<Tree *> myStack;
    Tree *cur = root;

    while(!myStack.empty() || cur) {
        if (cur) {
            cout << cur->data << " ";
            myStack.push(cur);
            cur = cur->left;
        } else {
            Tree *top = myStack.top();
            myStack.pop();
            cur = top->right;
        }
    }
}

void postOrder(Tree *root)
{
    stack<Tree *> myStack;
    Tree *cur = root;

    while(!myStack.empty() || cur) {
        if (cur) {
            myStack.push(cur);
            cur = cur->left;
        } else {
            while (!myStack.empty() && cur == myStack.top()->right) {
                cur = myStack.top();
                myStack.pop();
                getchar();
                cout << cur->data << " ";
            }
            cur = myStack.empty() ? NULL : myStack.top()->right;
        }
    }
}

void TreeToList(Tree *root, Tree *&head)
{
    if (!root) return;
    if (root->right) {
        TreeToList(root->right, head);
    }
    if (head) head->left = root;
    root->right = head;
    head = root;
    TreeToList(root->left, head);
}

Node *ListToTree(Tree *head)
{


}

int main(int argc, char **argv)
{
    int input[] = {21,7,5,6,3,2,1,4,6,23,43,54,12,54,8,10,11,35,56};
    //int input[] = {7};
    Tree *root = NULL, *root2 = NULL;
    int result;

    for (int i = 0; i < sizeof(input)/sizeof(int); i++) {
        TreeInsert(root, input[i]);
    }
    print_ascii_tree(root);
    int k = 6;
    Tree *head = NULL;
    TreeToList(root, head);
    while(head) {
        cout << head->data << " ";
        head = head->right;
    }
}
